{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Super Egg Drop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: superEggDrop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #鸡蛋掉落"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你 <code>k</code> 枚相同的鸡蛋，并可以使用一栋从第 <code>1</code> 层到第 <code>n</code> 层共有 <code>n</code> 层楼的建筑。</p>\n",
    "\n",
    "<p>已知存在楼层 <code>f</code> ，满足 <code>0 <= f <= n</code> ，任何从<strong> 高于</strong> <code>f</code> 的楼层落下的鸡蛋都会碎，从 <code>f</code> 楼层或比它低的楼层落下的鸡蛋都不会破。</p>\n",
    "\n",
    "<p>每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 <code>x</code> 扔下（满足 <code>1 <= x <= n</code>）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 <strong>重复使用</strong> 这枚鸡蛋。</p>\n",
    "\n",
    "<p>请你计算并返回要确定 <code>f</code> <strong>确切的值</strong> 的 <strong>最小操作次数</strong> 是多少？</p>\n",
    " \n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 1, n = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 \n",
    "否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 \n",
    "如果它没碎，那么肯定能得出 f = 2 。 \n",
    "因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 2, n = 6\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3, n = 14\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= k <= 100</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [super-egg-drop](https://leetcode.cn/problems/super-egg-drop/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [super-egg-drop](https://leetcode.cn/problems/super-egg-drop/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n2', '2\\n6', '3\\n14']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K: int, N: int) -> int:\n",
    "        @cache\n",
    "        def f1(k, n):\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            result = -1\n",
    "            left = 1\n",
    "            right = n + 1\n",
    "            while left < right:\n",
    "                mid = (left + right) >> 1\n",
    "                a = 1 + f1(k, n - mid)\n",
    "                b = 1 + f1(k - 1, mid - 1)\n",
    "                if a > b:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            a = 1 + f1(k, n - left)\n",
    "            b = 1 + f1(k - 1, left - 1)\n",
    "            result = max(a, b)\n",
    "            return result\n",
    "        return f1(K, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K, N):\n",
    "        \"\"\"\n",
    "        :type K: int\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [0] * (K + 1)\n",
    "        s = 0\n",
    "        while dp[K] < N:\n",
    "            for i in range(K, 0, -1):\n",
    "                dp[i] = 1 + dp[i] + dp[i - 1]\n",
    "            s += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K, N):\n",
    "        \"\"\"\n",
    "        :type K: int\n",
    "        :type N: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [0] * (K+1)\n",
    "        for m in range(1, N+1):\n",
    "            for e in range(K, 0, -1):\n",
    "                dp[e] += dp[e-1] + 1\n",
    "\n",
    "            if dp[-1] >= N:\n",
    "                return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K: int, N: int) -> int:\n",
    "        dp = [0]*(K+1)\n",
    "        m = 0\n",
    "        while dp[K] < N:\n",
    "            m += 1\n",
    "            for k in range(K, 0, -1):\n",
    "                # print(m, k)\n",
    "                dp[k] = dp[k - 1] + dp[k] + 1\n",
    "        return m\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K: int, N: int) -> int:\n",
    "        def max_floor(testcount):\n",
    "            ans, res = 0, 1\n",
    "            for i in range(1, K+1):\n",
    "                res*=(testcount-i+1)\n",
    "                res//=i \n",
    "                ans+=res\n",
    "                if ans >= N:\n",
    "                    return ans\n",
    "            return ans\n",
    "\n",
    "        l, r = 1, N\n",
    "        while l < r:\n",
    "            testcount = (l + r)//2\n",
    "            if max_floor(testcount) >= N:\n",
    "                r = testcount\n",
    "            else:\n",
    "                l = testcount + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def dp(K, N):\n",
    "#     for 1 <= i <= N:\n",
    "#         # 最坏情况下的最少扔鸡蛋次数\n",
    "#         res = min(res, \n",
    "#                   max( \n",
    "#                         dp(K - 1, i - 1), # 碎\n",
    "#                         dp(K, N - i)      # 没碎\n",
    "#                      ) + 1 # 在第 i 楼扔了一次\n",
    "#                  )\n",
    "#     return res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K: int, N: int) -> int:\n",
    "        dp = [0] * (K + 1)\n",
    "        res = 0\n",
    "        while dp[K] < N:\n",
    "            res += 1\n",
    "            for k in range(K, 0, -1):\n",
    "                dp[k] = dp[k-1] + dp[k] + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K: int, N: int) -> int:        \n",
    "        # @lru_cache(None) #二分       \n",
    "        # def dfs(k,N):            \n",
    "        #     if k==1:return N\n",
    "        #     if N==0:return 0\n",
    "        #     res=float('inf')\n",
    "        #     # for i in range(1,N+1):\n",
    "        #     #     res = min(res,max(dfs(k,N-i),dfs(k-1,i-1))+1)\n",
    "        #     low,high = 1,N \n",
    "        #     while low<=high:\n",
    "        #         mid = (low+high)//2\n",
    "        #         broken = dfs(k-1,mid-1)\n",
    "        #         not_broken = dfs(k,N-mid)\n",
    "        #         if broken<not_broken:\n",
    "        #             low=mid+1\n",
    "        #             res = min(res,not_broken+1)\n",
    "        #         else:\n",
    "        #             high=mid-1\n",
    "        #             res = min(res,broken+1) \n",
    "        #     return res\n",
    "        # return dfs(K,N)\n",
    "        #动归\n",
    "        # dp = [[0]*(N+1) for _ in range(K+1)]\n",
    "        # for i in range(1,K+1):\n",
    "        #     for j in range(1,N+1):\n",
    "        #         dp[i][j] = dp[i][j-1]+dp[i-1][j-1]+1\n",
    "        #         if dp[K][j]>=N:\n",
    "        #             return j\n",
    "        @lru_cache(None) #自顶向下\n",
    "        def dfs(k,n):\n",
    "            if k==1:return n #1鸡蛋线性探测n步，n层楼\n",
    "            if n==1:return 1 #1步1层楼\n",
    "            return dfs(k-1,n-1)+dfs(k,n-1)+1 #k鸡蛋，n步，探测的最高楼层\n",
    "        \n",
    "        for n in range(1,N+1):\n",
    "            cur = dfs(K,n)\n",
    "            if cur>=N:return n #最高楼层超过N，返回步数\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [0] * (k+1)\n",
    "        res = 0\n",
    "        while dp[-1] < n:\n",
    "            res += 1\n",
    "            for i in range(k, 0, -1):\n",
    "                dp[i] += dp[i-1] + 1\n",
    "        return res\n",
    "# 以下参考自:https://github.com/Shellbye/Shellbye.github.io/issues/42#issuecomment-516282822\n",
    "# dp[k][m] 表示用 k 个鸡蛋移动 m 步可以“保证求解”的最大楼层数。\n",
    "\n",
    "# 我们先解释一下这句话中的几个概念：\n",
    "\n",
    "# 所谓“求解”，意思就是给定楼层 N，我们能否找到临界楼层 F(F <= N)，使得鸡蛋从 F 层掉落刚好不会被摔碎。所谓“保证求解”，意思就是即使每次丢鸡蛋的结果都很差，最终仍能求解。\n",
    "\n",
    "# 比如，给定 1 个鸡蛋移动 1 步，那么可以求解的最大楼层数为 1，即从 1 楼丢下，如果鸡蛋碎了，求得 F=0，如果鸡蛋没碎，求得 F=1。在这种情况下，假如我们给出一个 2 层的楼，就无法保证求解了，因为无论从哪一层丢出鸡蛋，都没有十足的把握能够一次求得 F，换句话说，虽然我们仍有一定的机会能够求解，但无法“保证求解”。\n",
    "\n",
    "# 下面回到正题：\n",
    "\n",
    "# 假设我们有 k 个鸡蛋可以移动 m 步，考虑某一步 t 应该在哪一层丢鸡蛋？一个正确的选择是在 dp[k-1][t-1] + 1 层丢鸡蛋，结果分两种情况：\n",
    "\n",
    "# 如果鸡蛋碎了，我们首先排除了该层以上的所有楼层（不管这个楼有多高），而对于剩下的 dp[k-1][t-1] 层楼，我们一定能用 k-1 个鸡蛋在 t-1 步内求解。因此这种情况下，我们总共可以求解无限高的楼层。可见，这是一种非常好的情况，但并不总是发生。\n",
    "\n",
    "# 如果鸡蛋没碎，我们首先排除了该层以下的 dp[k-1][t-1] 层楼，此时我们还有 k 个蛋和 t-1 步，那么我们去该层以上的楼层继续测得 dp[k][t-1] 层楼。因此这种情况下，我们总共可以求解 dp[k-1][t-1] + dp[k][t-1] + 1 层楼。\n",
    "\n",
    "# 容易想象，在所有 m 步中只要有一次出现了第一种情况，那么我们就可以求解无限高的楼层。但“保证求解”的定义要求我们排除一切运气成分，因此我们只得认为每次移动都遇到第二种情况。于是得到递推公式：\n",
    "\n",
    "# dp[k][t] = dp[k-1][t-1] + dp[k][t-1] + 1\n",
    "\n",
    "# 基本的问题已经解决了，但是我们还遗留了一个问题：为什么要选择在 dp[k-1][t-1] + 1 层丢鸡蛋？\n",
    "\n",
    "# 现在我们已经知道，如果我们每一步都在 dp[k-1][t-1] + 1 层丢鸡蛋，最终是一定能够求解的。但如果我们选择在更低的层或者更高的层丢鸡蛋会怎样呢？我们分两种情况讨论：\n",
    "\n",
    "# 在更低的楼层丢鸡蛋。没有意义,因为我们已经求得dp[k-1][t-1]的值。虽然同样能够“保证求解”，但最终得到的并不是“最大”楼层数，我们没有充分挖掘鸡蛋数和移动次数的潜力，最终求解时会剩余一定量的鸡蛋或移动次数。\n",
    "\n",
    "# 在更高的楼层丢鸡蛋。不妨假设高了一层，即在第 dp[k-1][t-1] + 2 层丢鸡蛋。如果鸡蛋碎掉了，我们仍然可以排除该层以上的所有楼层（不管这个楼有多高），但接下来就不好办了，因为我们剩下的 k-1 个鸡蛋在 t-1 步内只能“保证求解” dp[k-1][t-1] 的楼层，而现在剩余的楼层却是 dp[k-1][t-1] + 1，多了一层，因此无法“保证求解”！\n",
    "\n",
    "# 综上，我们用排除法证明了每一步都应该在第 dp[k-1][t-1] + 1 层丢鸡蛋。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = {}\n",
    "\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        m = 1\n",
    "        while self.getRes(k, m) < n:\n",
    "            m+=1\n",
    "        return m\n",
    "\n",
    "    def getRes(self, k, m):\n",
    "        # k个鸡蛋扔m次最多可以测多少楼层\n",
    "        if k==1:\n",
    "            return m\n",
    "        if m==1:\n",
    "            return 1\n",
    "\n",
    "        state = f'{k}-{m}'\n",
    "        if state in self.cache:\n",
    "            return self.cache[state]\n",
    "        \n",
    "        self.cache[state] = self.getRes(k, m-1) + self.getRes(k-1, m-1) + 1\n",
    "\n",
    "        return self.cache[state]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        # dp[k][m]的含义是k个鸡蛋，移动m次最多能够确定多少楼层\n",
    "        # 在这一层扔出去碎的时候，才能确定在这一层以上的楼层都会碎，\n",
    "        ## 此时我们还有k - 1个蛋，用m - 1次操作去确定，即dp[k - 1][m - 1]\n",
    "        # 不碎的时候，能确定在这一层以下的楼层都不会碎，\n",
    "        ## 此时我们还有k个蛋，用m - 1次操作去确定,即dp[k][m - 1]\n",
    "        # 状态转移方程为dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1\n",
    "        dp = [0] * (k + 1)\n",
    "        m = 0\n",
    "        while dp[k] < n:\n",
    "            m += 1\n",
    "            for i in range(k, 0, -1):\n",
    "                # 倒着走，二维数组dp[k][m]只由左上方dp[k - 1][m - 1]和正上方dp[k][m - 1]决定\n",
    "                # 所以可以先倒着更新第一行，再倒着更新第二行...\n",
    "                # 等式右边的dp[i - 1]和dp[i]都是上一个m的dp，即二维数组中上一行的数据\n",
    "                # 这样便用一维数组更新了二维数组\n",
    "                dp[i] = dp[i - 1] + dp[i] + 1 # 没碎的情况下可确定的楼层，碎了直接出结果不为最坏情况（ dp[k-1][m-1] + 1 层丢为最优丢的楼层）\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        # Right now, dp[i] represents dp(1, i)\n",
    "        dp = list(range(n + 1))\n",
    "        dp2 = [0] * (n + 1)\n",
    "        for k in range(2, k + 1):\n",
    "            # Now, we will develop dp2[i] = dp(j, i)\n",
    "            x = 1\n",
    "            for m in range(1, n + 1):\n",
    "                # Let's find dp2[m] = dp(j, m)\n",
    "                # Increase our optimal x while we can make our answer better.\n",
    "                # Notice max(dp[x-1], dp2[m-x]) > max(dp[x], dp2[m-x-1])\n",
    "                # is simply max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)).\n",
    "                while x < m and max(dp[x - 1], dp2[m - x]) >= max(dp[x], dp2[m - x - 1]):\n",
    "                    x += 1\n",
    "\n",
    "                # The final answer happens at this x.\n",
    "                dp2[m] = 1 + max(dp[x - 1], dp2[m - x])\n",
    "\n",
    "            dp = dp2[:]\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        # Right now, dp[i] represents dp(1, i)\n",
    "        dp = list(range(n + 1))\n",
    "        dp2 = [0] * (n + 1)\n",
    "        for k in range(2, k + 1):\n",
    "            # Now, we will develop dp2[i] = dp(j, i)\n",
    "            x = 1\n",
    "            for m in range(1, n + 1):\n",
    "                # Let's find dp2[m] = dp(j, m)\n",
    "                # Increase our optimal x while we can make our answer better.\n",
    "                # Notice max(dp[x-1], dp2[m-x]) > max(dp[x], dp2[m-x-1])\n",
    "                # is simply max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)).\n",
    "                while x < m and max(dp[x - 1], dp2[m - x]) >= max(dp[x], dp2[m - x - 1]):\n",
    "                    x += 1\n",
    "\n",
    "                # The final answer happens at this x.\n",
    "                dp2[m] = 1 + max(dp[x - 1], dp2[m - x])\n",
    "\n",
    "            dp = dp2[:]\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 定义dp数组用来存储中间状态\n",
    "        self.dp = dict()\n",
    "\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        if k == 1:\n",
    "            return n\n",
    "        if n == 0:# 这个初始状态容易搞错\n",
    "            return 0\n",
    "        # 避免重复计算\n",
    "        if (k,n) in self.dp:\n",
    "            return self.dp[(k,n)]\n",
    "        rst = inf\n",
    "        '''\n",
    "        # 顺序迭代，提交超时\n",
    "        for i in range(1,n+1):\n",
    "            # 状态转移方程\n",
    "            broken = self.superEggDrop(k-1,i-1)\n",
    "            not_broken = self.superEggDrop(k,n-i)\n",
    "            # 题中要求“最坏情况”所以内层取max，要求最少次数所以外层取min\n",
    "            rst = min(rst,max(broken,not_broken)+1)\n",
    "        '''\n",
    "        # 二分法查找，降低时间复杂度\n",
    "        left,right = 1,n+1\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            # 结合二分法的状态转移方程\n",
    "            broken = self.superEggDrop(k-1,mid-1)\n",
    "            not_broken = self.superEggDrop(k,n-mid)\n",
    "            if broken >= not_broken:# 鸡蛋破了,往下找\n",
    "                rst = min(rst,broken+1)\n",
    "                right = mid\n",
    "            else:# 鸡蛋没破，往上找\n",
    "                rst = min(rst,not_broken+1)\n",
    "                left = mid+1\n",
    "        self.dp[(k,n)] = rst\n",
    "        return rst\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 定义dp数组用来存储中间状态\n",
    "        self.dp = dict()\n",
    "\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        if k == 1:\n",
    "            return n\n",
    "        if n == 0:# 这个初始状态容易搞错\n",
    "            return 0\n",
    "        # 避免重复计算\n",
    "        if (k,n) in self.dp:\n",
    "            return self.dp[(k,n)]\n",
    "        rst = inf\n",
    "        '''\n",
    "        # 顺序迭代，提交超时\n",
    "        for i in range(1,n+1):\n",
    "            # 状态转移方程\n",
    "            broken = self.superEggDrop(k-1,i-1)\n",
    "            not_broken = self.superEggDrop(k,n-i)\n",
    "            # 题中要求“最坏情况”所以内层取max，要求最少次数所以外层取min\n",
    "            rst = min(rst,max(broken,not_broken)+1)\n",
    "        '''\n",
    "        # 二分法查找，降低时间复杂度\n",
    "        left,right = 1,n+1\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            # 结合二分法的状态转移方程\n",
    "            broken = self.superEggDrop(k-1,mid-1)\n",
    "            not_broken = self.superEggDrop(k,n-mid)\n",
    "            if broken >= not_broken:# 鸡蛋破了,往下找\n",
    "                rst = min(rst,broken+1)\n",
    "                right = mid\n",
    "            else:# 鸡蛋没破，往上找\n",
    "                rst = min(rst,not_broken+1)\n",
    "                left = mid+1\n",
    "        self.dp[(k,n)] = rst\n",
    "        return rst\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def getResults(k,n):\n",
    "    if k==1:\n",
    "        return n\n",
    "    if n==0:\n",
    "        return 0\n",
    "    else:\n",
    "        l=1\n",
    "        r=n\n",
    "        while l<r-1:\n",
    "            mid=(l+r)>>1\n",
    "            a=getResults(k-1,mid-1)\n",
    "            b=getResults(k,n-mid)\n",
    "            if a<b:\n",
    "                l=mid\n",
    "            if a>b:\n",
    "                r=mid\n",
    "            if a==b:\n",
    "                l=r=mid\n",
    "                break\n",
    "        return 1+min(max(getResults(k-1,mid-1),getResults(k,n-mid)) for mid in [l,r])\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        return getResults(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  ans = dict()\n",
    "  def superEggDrop(self, k: int, n: int) -> int:\n",
    "    def p(k, n):\n",
    "      if (k,n) in self.ans:\n",
    "        return self.ans[(k, n)]\n",
    "      #print((k,n))\n",
    "      if k == 1 or n == 1 or n == 0:\n",
    "        self.ans[(k,n)] = n\n",
    "        return n\n",
    "      # Drop at floor d.\n",
    "      # If it breaks, the new search range is [1, ..., d-1]\n",
    "      # If it holds, the new search range is [d+1, ..., n]\n",
    "      # k-1, d-1; k, n-d\n",
    "      left = 1\n",
    "      right = n-1\n",
    "      while left < right:\n",
    "        mid = left + (right-left)//2\n",
    "        if p(k-1, mid) - p(k, n-mid-1) < 0:\n",
    "          left = mid+1\n",
    "        elif p(k-1, mid) - p(k, n-mid-1) == 0:\n",
    "          left = mid\n",
    "          right = mid\n",
    "          break\n",
    "        elif p(k-1, mid) - p(k, n-mid-1) > 0:\n",
    "          right = mid-1\n",
    "      \n",
    "      self.ans[(k,n)] = min([max(p(k-1, left), p(k, n-left-1)), max(p(k-1, right), p(k, n-right-1))])+1\n",
    "      return self.ans[(k,n)]\n",
    "    p0 = p(k, n)\n",
    "    #print(self.ans)\n",
    "    return p0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "nn = [0, 0]\n",
    "cache = dict()\n",
    "def egg(k: int, n: int) -> int:\n",
    "    nn[1] += 1\n",
    "    if (n == 0):\n",
    "        return 0\n",
    "    if (n == 1):\n",
    "        return 1\n",
    "    if (k == 1):\n",
    "        return n\n",
    "    if ((k, n) in cache):\n",
    "        return cache[(k, n)]\n",
    "    \n",
    "    nn[0] += 1\n",
    "    \n",
    "    res = None\n",
    "    l = 1\n",
    "    r = n+1\n",
    "    while (l + 1 < r):\n",
    "        m = (l + r) // 2\n",
    "        n1 = egg(k-1, m-1)\n",
    "        n2 = egg(k,n-m)\n",
    "        if (n1 == n2):\n",
    "            res = 1 + n1\n",
    "            break\n",
    "        elif (n1 < n2):\n",
    "            l = m\n",
    "        else:\n",
    "            r = m\n",
    "    else:\n",
    "        m = (l + r) // 2\n",
    "        n1 = egg(k-1, m-1)\n",
    "        n2 = egg(k,n-m)\n",
    "        res = 1 + max(n1, n2)\n",
    "\n",
    "    cache[(k, n)] = res\n",
    "    return res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        a= egg(k, n)\n",
    "        print(nn)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        self.memo = {}\n",
    "\n",
    "        def dp(k, n):\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0 or n == 1:\n",
    "                return n\n",
    "            if (k, n) in self.memo:\n",
    "                return self.memo[(k, n)]\n",
    "            res = float(\"INF\")\n",
    "\n",
    "            # for i in range(1, n + 1):\n",
    "            #     res = min(res, max(dp(k - 1, i - 1), dp(k, n - i)) + 1)\n",
    "\n",
    "            # 根据单调性想到 用二分搜索代替线性搜索\n",
    "            left = 1\n",
    "            right = n\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                broken = dp(k - 1, mid - 1) + 1\n",
    "                unbroken = dp(k, n - mid) + 1\n",
    "                if broken == unbroken:\n",
    "                    res = broken\n",
    "                    break\n",
    "                elif broken < unbroken:\n",
    "                    res = min(res, unbroken)\n",
    "                    left = mid + 1\n",
    "                elif broken > unbroken:\n",
    "                    res = min(res, broken)\n",
    "                    right = mid - 1\n",
    "\n",
    "            self.memo[(k, n)] = res\n",
    "            return res\n",
    "        \n",
    "        return dp(k, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = []\n",
    "        for i in range(k+1):\n",
    "            dp.append([0]*(n+1))\n",
    "        \n",
    "        m=0\n",
    "        while dp[k][m]<n:\n",
    "            m+=1\n",
    "            for i in range(1,k+1):\n",
    "                dp[i][m] = dp[i][m-1]+dp[i-1][m-1]+1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        self.memo = [[-1] * (n + 1) for _ in range(k + 1)]\n",
    "        return self.dp(k, n)\n",
    "    \n",
    "    def dp(self, k, n):\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if k == 1:\n",
    "            return n\n",
    "        if self.memo[k][n] != -1:\n",
    "            return self.memo[k][n]\n",
    "        lo, hi = 1, n\n",
    "        res = n\n",
    "        while lo <= hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            broken = self.dp(k - 1, mid - 1)\n",
    "            not_broken = self.dp(k, n - mid)\n",
    "            if broken > not_broken:\n",
    "                hi = mid - 1\n",
    "                res = min(res, broken + 1)\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "                res = min(res, not_broken + 1)\n",
    "        self.memo[k][n] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\r\n",
    "        f=[[0]*(n+1) for _ in range(k+1)]\r\n",
    "        for m in range(1,n+1):\r\n",
    "            for K in range(1,k+1):\r\n",
    "                f[K][m]=f[K][m-1]+f[K-1][m-1]+1\r\n",
    "            if f[k][m]>=n:\r\n",
    "                return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        memo={}\n",
    "        def dp(K,N):\n",
    "            if K==1:\n",
    "                return N\n",
    "            if N==0:\n",
    "                return 0\n",
    "            if (K,N) in memo:\n",
    "                return memo[(K,N)]\n",
    "            \n",
    "            # res=float('inf')\n",
    "            # for i in range(1,N+1):\n",
    "            #     res=min(res,max(dp(K-1,i-1),dp(K,N-i))+1)\n",
    "            \n",
    "            #二分法找最小值\n",
    "            res=float('inf')\n",
    "            left=1\n",
    "            right=N\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if dp(K,N-mid)>dp(K-1,mid-1):\n",
    "                    res=min(res,dp(K,N-mid)+1)\n",
    "                    left=mid+1\n",
    "                elif dp(K,N-mid)<dp(K-1,mid-1):\n",
    "                    res=min(res,dp(K-1,mid-1)+1)\n",
    "                    right=mid-1\n",
    "                else:\n",
    "                    res=min(res,dp(K,N-mid)+1)\n",
    "                    break\n",
    "\n",
    "\n",
    "\n",
    "            memo[(K,N)]=res\n",
    "            return res\n",
    "        return dp(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "f = [[0]*(10001) for _ in range(101)]\n",
    "\n",
    "for i in range(1, 101):\n",
    "    x = 1\n",
    "    for j in range(1, 10001):\n",
    "        if i == 1:\n",
    "            f[i][j] = j \n",
    "        elif j == 1:\n",
    "            f[i][j] = 1\n",
    "        else:     \n",
    "\n",
    "            while x <= j:\n",
    "                t = f[i][j-x]-f[i-1][x-1]\n",
    "                if t > 0:\n",
    "                    f[i][j] = 1 + max(f[i][j-x], f[i-1][x-1])\n",
    "                    x += 1\n",
    "                elif t == 0:\n",
    "                    f[i][j] = 1 + max(f[i][j-x], f[i-1][x-1])\n",
    "                    break\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        \n",
    "        return f[k][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "\n",
    "        if n== 1:\n",
    "            return 1\n",
    "\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        ans = -1\n",
    "        \n",
    "        # for k_ in range(1,k+1):\n",
    "        #     dp[1][k_] = 1\n",
    "\n",
    "        for t in range(1, n+1):\n",
    "            for k_ in range(1, k+1):\n",
    "                dp[t][k_] = 1 + dp[t-1][k_] + dp[t-1][k_-1]\n",
    "            if dp[t][k] >= n:\n",
    "                ans = t\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[0 for _ in range(k+1)] for _ in range(n+1)]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][1] = i\n",
    "\n",
    "        for j in range(2,k+1):\n",
    "            t =1\n",
    "            for i in range(1,n+1):\n",
    "                dp[i][j] = i\n",
    "                while t<i and dp[t-1][j-1]<dp[i-t][j]:\n",
    "                    t+=1\n",
    "                dp[i][j] = min(dp[i][j],max(dp[t-1][j-1],dp[i-t][j])+1)\n",
    "                #     dp[i][j] = min(dp[i][j],max(dp[t-1][j-1],dp[i-t][j])+1)\n",
    "                # left = 1\n",
    "                # right = i\n",
    "                \n",
    "                # while left<right:\n",
    "                #     t = (left+right)//2\n",
    "                #     bre = dp[t-1][j-1]\n",
    "                #     nobre = dp[i-t][j]\n",
    "                #     if bre <= nobre:\n",
    "                #         left = t+1\n",
    "                #         dp[i][j] = min(dp[i][j],max(dp[t-1][j-1],dp[i-t][j])+1)\n",
    "                #     else:\n",
    "                #         right = t-1\n",
    "                #         dp[i][j] = min(dp[i][j],max(dp[t-1][j-1],dp[i-t][j])+1)\n",
    "                # t = left\n",
    "                # dp[i][j] = min(dp[i][j],max(dp[t-1][j-1],dp[i-t][j])+1)\n",
    "                \n",
    "                \n",
    "        return dp[-1][-1]\n",
    "\n",
    "        \n",
    "\n",
    "    \n",
    "      \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][1] = i\n",
    "            dp[i][0] = float(\"inf\")\n",
    "        for w in range(2, k + 1):\n",
    "            for i in range(1, n + 1):\n",
    "                # res = float(\"inf\")\n",
    "                # for j in range(1, i + 1):\n",
    "                #     res = min(res, max(dp[j-1][w-1], dp[i-j][w]) + 1)\n",
    "                # dp[i][w] = res  \n",
    "                start, end = 1, i\n",
    "                while start + 1 < end:\n",
    "                    mid = (start + end) // 2\n",
    "                    if dp[mid-1][w-1] < dp[i - mid][w]:\n",
    "                        start = mid\n",
    "                    elif dp[mid-1][w-1] > dp[i - mid][w]:\n",
    "                        end = mid\n",
    "                    else:\n",
    "                        start = end = mid\n",
    "                dp[i][w] = min(max(dp[start-1][w-1], dp[i-start][w]),\n",
    "                               max(dp[end-1][w-1], dp[i-end][w])) + 1\n",
    "        return dp[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        memo = {}\n",
    "        def dp(k,n):\n",
    "            if (k,n) not in memo:\n",
    "                if n == 0:\n",
    "                    ans = 0\n",
    "                elif k == 1:\n",
    "                    ans = n\n",
    "                else:\n",
    "                    lo, hi = 1,n\n",
    "                    # keep a gap of 2 values to manually check later\n",
    "                    while lo + 1 < hi:\n",
    "                        x = (lo + hi) // 2\n",
    "                        t1 = dp(k - 1, x - 1)\n",
    "                        t2 = dp(k, n - x)\n",
    "                        if t1 < t2:\n",
    "                            lo = x\n",
    "                        elif t1 > t2:\n",
    "                            hi = x\n",
    "                        else:\n",
    "                            lo = hi = x\n",
    "                    ans = 1 + min(max(dp(k - 1, x - 1),dp(k, n - x)) for x in [lo,hi])\n",
    "                memo[k,n] = ans\n",
    "            return memo[k,n]\n",
    "        return dp(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        memo = {}\n",
    "        def dp(k, n):\n",
    "            if (k, n) not in memo:\n",
    "                if n == 0:\n",
    "                    ans = 0\n",
    "                elif k == 1:\n",
    "                    ans = n\n",
    "                else:\n",
    "                    lo, hi = 1, n\n",
    "                    # keep a gap of 2 x values to manually check later\n",
    "                    while lo+1 < hi:\n",
    "                        x = (lo + hi) // 2\n",
    "                        t1 = dp(k - 1, x - 1)\n",
    "                        t2 = dp(k, n - x)\n",
    "\n",
    "                        if t1 < t2:\n",
    "                            lo = x\n",
    "                            \n",
    "                        elif t1 > t2:\n",
    "                            hi = x\n",
    "                        else:\n",
    "                            lo = hi = x\n",
    "                    print(lo,hi)\n",
    "\n",
    "                    ans = 1 + max(dp(k - 1, lo - 1), dp(k, n - lo))\n",
    "                                #   for x in (lo, hi))\n",
    "\n",
    "                memo[k, n] = ans\n",
    "            return memo[k, n]\n",
    "        return dp(k, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp=[[0]*(n+1) for _ in range(k+1)]\n",
    "        m=0\n",
    "        for m in range(1,n+1):\n",
    "            for i in range(1,k+1):\n",
    "                dp[i][m]=dp[i-1][m-1]+dp[i][m-1]+1\n",
    "            if(dp[k][m]>=n):\n",
    "                break\n",
    "        print(dp)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        # 转化为01背包问题，思路见Onenote笔记\n",
    "        if n == 1 : return 1\n",
    "\n",
    "        dp = [[0 for j in range(k + 1)] for i in range(n + 1)]\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1\n",
    "            if dp[i][k] >= n:\n",
    "                print(dp)\n",
    "                return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for j in range(1, k + 1):\n",
    "            dp[1][j] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][1] = i\n",
    "        print(dp)\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(2, k + 1):\n",
    "                lo, hi = 1, i\n",
    "                same = False\n",
    "                while lo < hi:\n",
    "                    mid = (lo + hi) // 2\n",
    "                    left, right = dp[i - mid][j] , dp[mid - 1][j - 1]\n",
    "                    if left > right:\n",
    "                        lo = mid + 1\n",
    "                    elif left < right:\n",
    "                        hi = mid\n",
    "                    else:\n",
    "                        same = True\n",
    "                        lo = mid\n",
    "                        break\n",
    "                cands = [lo, lo + 1] if not same else [lo, lo]\n",
    "                dp[i][j] = 1 + min([max(dp[i - x][j], dp[x - 1][j - 1]) for x in cands])\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[0]*n for _ in range(k)]\n",
    "        dp[0] = [i+1 for i in range(n)]\n",
    "        for j in range(1,k):\n",
    "            for i in range(n):\n",
    "                dp[j][i] = i+1\n",
    "                l,r = 0,i\n",
    "                while l+1<r:\n",
    "                    mid = (l+r)//2\n",
    "                    a = dp[j-1][mid-1] if mid -1 >= 0 else 0\n",
    "                    b = dp[j][i-mid-1] if i-mid-1 >= 0 else 0      \n",
    "                    dp[j][i] = min(dp[j][i], max(a,b)+1 )               \n",
    "                    if a > b :\n",
    "                        r = mid\n",
    "                    elif a < b:\n",
    "                        l = mid\n",
    "                    else:\n",
    "                        l = r = mid\n",
    "                \n",
    "                # for t in (l,r):\n",
    "                #     a = dp[j-1][t-1] if t -1 >= 0 else 0\n",
    "                #     b = dp[j][i-t-1] if i-t-1 >= 0 else 0 \n",
    "                #     dp[j][i] = min(dp[j][i], max(a,b)+1 )\n",
    "\n",
    "                    \n",
    "                \n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[inf]*(n+1) for _ in range(k+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[1][i] = i\n",
    "            dp[0][i] = 0\n",
    "        for i in range(k+1):\n",
    "            dp[i][1] = 1\n",
    "            dp[i][0] = 0\n",
    "        for i in range(2,k+1):\n",
    "            for j in range(2,n+1):\n",
    "                left = 0\n",
    "                right = j\n",
    "                while left+1<right:\n",
    "                    mid = (left+right)//2\n",
    "                    t1 = dp[i-1][mid-1]\n",
    "                    t2 = dp[i][j-mid]\n",
    "                    if t1 < t2:\n",
    "                        left = mid\n",
    "                    elif t1 > t2:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = right =mid\n",
    "                dp[i][j] = max(dp[i-1][mid-1],dp[i][j-mid]) + 1\n",
    "        print(dp)\n",
    "        return dp[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 【用计划递归】+ 【二分搜索】  ->  核心是穷举\n",
    "# 一个关键的问题：这个【最小值】其实是“试出来”的，即：尝试分别在1-100层扔鸡蛋，【最坏】情况下，正确楼层在剩余尝试次数多的那一边（也就是鸡蛋碎和没碎中比较差的情况，剩余尝试次数多的那种情况），所以取max意味着考虑每种尝试位置的【最坏】情况，然后外边再套一层min，意味着在众多最坏情况下取最小值——“最优的方案、在最坏情况下”：需要多少次？\n",
    "# 1. 取max是因为要求的是“最坏情况”，也就是要找无论 起始楼层 的初始值如何的条件下的查找次数\n",
    "#    蛋破碎一定发生在搜索区间穷尽时，不会说你在第 1 层摔一下鸡蛋就碎了，这是你运气好，不是最坏情况。\n",
    "# 2. 什么叫「至少」要扔几次？\n",
    "#    如果不限制鸡蛋个数的话，二分思路显然可以得到最少尝试的次数\n",
    "#    但问题是，现在给你了鸡蛋个数的限制 K，直接使用二分思路就不行了。\n",
    "# 3. dp数组的定义：dp[k][n]表示当前有 K 个鸡蛋，面对 N 层楼，需要最少的扔dp次鸡蛋\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        # dp[i][j]表示用i个蛋，一共j层楼的最坏尝试次数\n",
    "        memo = [[float(\"inf\")] * (n + 1) for _ in range(k + 1)]\n",
    "        def dp(k, n, memo):\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if memo[k][n] != float(\"inf\"):\n",
    "                return memo[k][n]\n",
    "            l = 1\n",
    "            r = n\n",
    "            res = float(\"inf\")\n",
    "            while l <= r:\n",
    "                mid = l + (r - l) // 2\n",
    "                broken = dp(k - 1, mid - 1, memo) + 1\n",
    "                not_broken = dp(k, n - mid, memo) + 1\n",
    "                if broken > not_broken:\n",
    "                    r = mid - 1\n",
    "                    res = min(res, broken)\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "                    res = min(res, not_broken)\n",
    "            memo[k][n] = res\n",
    "            return res\n",
    "        \n",
    "        ans = dp(k, n, memo)\n",
    "        print(memo)\n",
    "        return ans\n",
    "        # return memo[-1][-1]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp_table = []\n",
    "        for i in range(k+1):\n",
    "            dp_table.append([-1] * (n+1))\n",
    "\n",
    "        def dp(K, N):\n",
    "            if K == 1:\n",
    "                return N\n",
    "            if N == 0:\n",
    "                return 0\n",
    "            if dp_table[K][N] != -1:\n",
    "                return dp_table[K][N]\n",
    "            res = N\n",
    "            l, r = 1, N\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                broken = dp(K-1, mid-1)\n",
    "                nbroken = dp(K, N-mid)\n",
    "                if broken > nbroken:\n",
    "                    r = mid-1\n",
    "\n",
    "                    res = min(res, broken+1)\n",
    "                else:\n",
    "                    l = mid+1\n",
    "                    res= min(res, nbroken+1)\n",
    "            dp_table[K][N] = res\n",
    "            return res\n",
    "        # print(dp_table)\n",
    "        return dp(k, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp_table = []\n",
    "        for i in range(k+1):\n",
    "            dp_table.append([-1] * (n+1))\n",
    "\n",
    "        def dp(K, N):\n",
    "            if K == 1:\n",
    "                return N\n",
    "            if N == 0:\n",
    "                return 0\n",
    "            if dp_table[K][N] != -1:\n",
    "                return dp_table[K][N]\n",
    "            res = N\n",
    "            l, r = 1, N\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                broken = dp(K-1, mid-1)\n",
    "                nbroken = dp(K, N-mid)\n",
    "                if broken >= nbroken:\n",
    "                    r = mid-1\n",
    "                    res = min(res, broken+1)\n",
    "                else:\n",
    "                    l = mid+1\n",
    "                    res= min(res, nbroken+1)\n",
    "            dp_table[K][N] = res\n",
    "            return res\n",
    "        # print(dp_table)\n",
    "        return dp(k, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        memo = [[-1 for _ in range(n)] for _ in range(k)]\n",
    "        def dp(k, n):\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if memo[k-1][n-1] != -1:\n",
    "                return memo[k-1][n-1]\n",
    "            res = n\n",
    "            lo, hi = 1, n\n",
    "            while lo + 1 < hi:\n",
    "                mid = lo + (hi - lo) // 2\n",
    "                t1 = dp(k-1, mid - 1)\n",
    "                t2 = dp(k, n - mid)\n",
    "\n",
    "                if t1 < t2:\n",
    "                    lo = mid\n",
    "                elif t1 > t2:\n",
    "                    hi = mid\n",
    "                elif t1 == t2:\n",
    "                    lo = hi = mid\n",
    "\n",
    "            memo[k-1][n-1] = min(max(dp(k-1, lo-1), dp(k, n - lo)),\n",
    "                                 max(dp(k-1, hi-1), dp(k, n-hi))) + 1\n",
    "            return memo[k-1][n-1]\n",
    "        return dp(k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        memo = [[-1]*(n+1) for _ in range(k+1)]\n",
    "        def dp(k,n):\n",
    "            if n == 0: return 0\n",
    "            if k == 1: return n\n",
    "            if memo[k][n] != -1: return memo[k][n]\n",
    "            left,right = 1,n\n",
    "            while left+1<right:\n",
    "                mid = left+right>>1\n",
    "                t1,t2 = dp(k,n-mid),dp(k-1,mid-1)\n",
    "                if t1 == t2: left = right = mid\n",
    "                elif t1<t2: right = mid\n",
    "                else: left = mid\n",
    "            ans = min(max(dp(k,n-x),dp(k-1,x-1)) for x in range(left,right+1))+1\n",
    "            memo[k][n] = ans\n",
    "            return memo[k][n]\n",
    "        return dp(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @functools.cache\n",
    "    def func(self, k, n):\n",
    "        if k == 1:\n",
    "            return n\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        ret = n\n",
    "        l = 1\n",
    "        r = n\n",
    "        while l+1 < r:\n",
    "            mid = (l+r)//2\n",
    "            a = self.func(k-1, mid-1)\n",
    "            b = self.func(k, n-mid)\n",
    "            if a < b:\n",
    "                l = mid\n",
    "            elif a > b:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = r = mid\n",
    "        for i in range(l, r+1):\n",
    "            ret = min(ret, max(self.func(k-1, i-1), self.func(k, n-i)) + 1)\n",
    "        return ret\n",
    "\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        return self.func(k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\r\n",
    "        memo={}\r\n",
    "        def dp(k,n):\r\n",
    "            if k==1:\r\n",
    "                return n\r\n",
    "            if n==0:\r\n",
    "                return 0\r\n",
    "            if (k,n) in memo:\r\n",
    "                return memo[(k,n)]\r\n",
    "            ans=float('inf')\r\n",
    "            left,right=1,n\r\n",
    "            while left<=right:\r\n",
    "                mid=(left+right)//2\r\n",
    "                broken=dp(k-1,mid-1)\r\n",
    "                not_broken=dp(k,n-mid)\r\n",
    "                if broken>=not_broken:\r\n",
    "                    ans=min(ans,broken)\r\n",
    "                    right=mid-1\r\n",
    "                else:\r\n",
    "                    left=mid+1\r\n",
    "                    ans=min(ans,not_broken)\r\n",
    "            ans+=1\r\n",
    "            memo[(k,n)]=ans\r\n",
    "            return ans\r\n",
    "        return dp(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        if k == 1: return n\n",
    "        if n <= 2: return n\n",
    "        next_min = n\n",
    "        startI = 2\n",
    "        endI = n\n",
    "        while startI>1 and endI<=n and startI<endI:\n",
    "            i = startI+(endI-startI)//2\n",
    "            l = self.superEggDrop(k-1, i-1)\n",
    "            r = self.superEggDrop(k, n-i)\n",
    "            # print(l, r, i)\n",
    "            next = max(l, r)\n",
    "            if next<next_min: next_min = next\n",
    "            if l==r: break\n",
    "            if l<r: startI = i+1\n",
    "            else: endI = i\n",
    "        return 1+next_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dp = dict()\n",
    "\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        def dp_fun(k,n):\n",
    "            if k==1:\n",
    "                return n\n",
    "            if n==0:\n",
    "                return 0\n",
    "            if (k,n) in self.dp:\n",
    "                return self.dp[(k,n)]\n",
    "            rst = inf\n",
    "            '''\n",
    "            for i in range(1,n+1):\n",
    "                broken = dp_fun(k-1,i-1)\n",
    "                not_broken = dp_fun(k,n-i)\n",
    "                rst = min(rst,max(broken,not_broken)+1)\n",
    "            '''\n",
    "            left,right = 1,n+1\n",
    "            while left < right:\n",
    "                mid = (left+right)//2\n",
    "                broken = dp_fun(k-1,mid-1)\n",
    "                not_broken = dp_fun(k,n-mid)\n",
    "                if broken>=not_broken:\n",
    "                    rst = min(rst,broken+1)\n",
    "                    right = mid\n",
    "                else:\n",
    "                    rst = min(rst,not_broken+1)\n",
    "                    left = mid+1\n",
    "            self.dp[(k,n)] = rst\n",
    "            return rst\n",
    "        return dp_fun(k,n)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        memo = dict()\n",
    "        def dp(k,n):\n",
    "            if k==1:\n",
    "                return n\n",
    "            if n==0:\n",
    "                return 0\n",
    "            if (k,n) in memo:\n",
    "                return memo[(k,n)]\n",
    "            res = float(\"inf\")\n",
    "            l = 1\n",
    "            r = n\n",
    "            while l<=r:\n",
    "                mid = (l+r)//2\n",
    "                broken = dp(k-1,mid-1)\n",
    "                not_broken = dp(k,n-mid)\n",
    "                if broken >= not_broken:\n",
    "                    r = mid-1\n",
    "                    res = min(res,broken+1)\n",
    "                else:\n",
    "                    l = mid+1\n",
    "                    res = min(res,not_broken+1)\n",
    "            memo[(k,n)]=res\n",
    "            return res\n",
    "        return dp(k,n)        \n",
    " \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "\n",
    "        # def dp(n, k):\n",
    "        #     if k == 1:\n",
    "        #         return n\n",
    "        #     if n == 0:\n",
    "        #         return 0\n",
    "\n",
    "        #     if memo[n][k] != -1:\n",
    "        #         return memo[n][k]\n",
    "\n",
    "        #     res = float('inf')\n",
    "        #     for i in range(1, n + 1):\n",
    "        #         res = min(res, \n",
    "        #             max(\n",
    "        #                 dp(i - 1, k - 1), \n",
    "        #                 dp(n - i, k)\n",
    "        #             ) + 1\n",
    "        #         )\n",
    "        #     memo[n][k] = res\n",
    "        #     return memo[n][k]\n",
    "\n",
    "        # memo = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        # return dp(n, k)\n",
    "\n",
    "        def dp(n, k):\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "\n",
    "            if memo[n][k] != -1:\n",
    "                return memo[n][k]\n",
    "\n",
    "            res = float('inf')\n",
    "\n",
    "            left, right = 1, n\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                broken = dp(mid - 1, k - 1)\n",
    "                not_broken = dp(n - mid, k)\n",
    "                if broken > not_broken:\n",
    "                    right = mid - 1\n",
    "                    res = min(res, broken + 1)\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "                    res = min(res, not_broken + 1)\n",
    "\n",
    "            memo[n][k] = res\n",
    "            return memo[n][k]\n",
    "\n",
    "        memo = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        return dp(n, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(k, n):\n",
    "            if k == 1: return n\n",
    "            if n == 0: return 0\n",
    "            res = n\n",
    "            l, r = 1, n\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                broken = dfs(k-1, mid-1) + 1\n",
    "                not_broken = dfs(k, n-mid) + 1\n",
    "                if broken >= not_broken:\n",
    "                    r = mid\n",
    "                    res = min(res, broken)\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "                    res = min(res, not_broken)\n",
    "            # for i in range(1, n + 1):\n",
    "            #     res = min(res, max(dfs(k-1, i-1), dfs(k, n - i)) + 1)\n",
    "            return res\n",
    "        return dfs(k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def superEggDrop(self, k: int, n: int) -> int:\n",
    "    #     # 1.DP solution, this will TLE\n",
    "    #     # time complexity: O(N^2*K)\n",
    "    #     # space complexity: O(N*K)\n",
    "    #     '''\n",
    "    #     dp[n][k] means that given k eggs and n moves, what is the minimum number of moves for checking the floor which will break the egg\n",
    "    #     '''\n",
    "\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     @lru_cache(None)\n",
    "    #     def dp(i: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             return 0\n",
    "    #         if k == 1:\n",
    "    #             return i\n",
    "\n",
    "    #         min_attempts = float(\"inf\")\n",
    "    #         for j in range(1, i + 1):\n",
    "    #             # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "    #             # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "    #             broken = dp(j - 1, k - 1)\n",
    "    #             not_broken = dp(i - j, k)\n",
    "\n",
    "    #             # chose the worst case\n",
    "    #             current_attempts = 1 + max(broken, not_broken)\n",
    "    #             # select the best case from the worst cases\n",
    "    #             min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "    #         return min_attempts\n",
    "\n",
    "    #     return dp(n, k)\n",
    "\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        # 2.DP solution with binary search optimization, this will success\n",
    "        # time complexity: O(N^2*K)\n",
    "        # space complexity: O(N*K)\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, k: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return i\n",
    "\n",
    "            # this idea is important!\n",
    "            # find the crossing point of dp(x-1,k-1) and dp(n-x,k)\n",
    "            l, r = 1, i + 1\n",
    "            while l <= r:\n",
    "                # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "                # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "\n",
    "                j = (l + r) >> 1\n",
    "                broken = dp(j - 1, k - 1)\n",
    "                not_broken = dp(i - j, k)\n",
    "                if broken < not_broken:\n",
    "                    l = j + 1\n",
    "                else:\n",
    "                    r = j - 1\n",
    "\n",
    "            mid = l\n",
    "            return 1 + max(dp(mid - 1, k - 1), dp(i - mid, k))\n",
    "\n",
    "        return dp(n, k)\n",
    "\n",
    "    # def superEggDrop(self, k: int, n: int) -> int:\n",
    "    #     # 3.DP solution with binary search optimization, this will success\n",
    "    #     # time complexity: O(N^2*K)\n",
    "    #     # space complexity: O(N*K)\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     @lru_cache(None)\n",
    "    #     def dp(i: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             return 0\n",
    "    #         if k == 1:\n",
    "    #             return i\n",
    "\n",
    "    #         min_attempts = float(\"inf\")\n",
    "    #         l, r = 1, i + 1\n",
    "    #         while l <= r:\n",
    "    #             # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "    #             # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "\n",
    "    #             j = (l + r) >> 1\n",
    "    #             broken = dp(j - 1, k - 1)\n",
    "    #             not_broken = dp(i - j, k)\n",
    "\n",
    "    #             # chose the worst case\n",
    "    #             current_attempts = 1 + max(broken, not_broken)\n",
    "    #             # select the best case from all worst cases\n",
    "    #             min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "    #             if broken < not_broken:\n",
    "    #                 l = j + 1\n",
    "    #             else:\n",
    "    #                 r = j - 1\n",
    "\n",
    "    #         return min_attempts\n",
    "\n",
    "    #     return dp(n, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(k,n):\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            l,r = 0,n + 1\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) >> 1\n",
    "                t1,t2 = dfs(k - 1,mid - 1),dfs(k,n - mid)\n",
    "                # t1递增，t2递减\n",
    "                if t1 < t2:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "                ans = min(ans,max(t1,t2) + 1)\n",
    "            return ans\n",
    "\n",
    "        return dfs(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "\n",
    "        dp = [[inf] * (n + 1) for _ in range(k + 1)]\n",
    "        dp0 = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "\n",
    "        #初始化\n",
    "        #只有一颗鸡蛋\n",
    "        for nn in range(n + 1):\n",
    "            dp0[1][nn] = 1\n",
    "            dp[1][nn] = nn\n",
    "\n",
    "        #只有一层楼\n",
    "        for kk in range(k + 1):\n",
    "            dp0[kk][1] = 1\n",
    "            dp[kk][1] = 1\n",
    "\n",
    "            dp0[kk][0] = 0\n",
    "            dp[kk][0] = 0\n",
    "\n",
    "\n",
    "\n",
    "        for kk in range(2, k + 1):\n",
    "            for nn in range(2, n + 1):\n",
    "                #1.找到决策点\n",
    "                i = dp0[kk][nn-1]\n",
    "                \n",
    "                while i < nn:\n",
    "                    if dp[kk][nn-i-1] > dp[kk-1][i]:\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                p1 = max(dp[kk][nn-i], dp[kk-1][i-1])\n",
    "                p2 = max(dp[kk][nn-i-1], dp[kk-1][i])        \n",
    "                if p1 < p2:\n",
    "                    dp[kk][nn] = p1 + 1\n",
    "                    dp0[kk][nn] = i\n",
    "                else:\n",
    "                    dp[kk][nn] = p2 + 1\n",
    "                    dp0[kk][nn] = i+1   \n",
    "                \n",
    "        #print(dp)\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(k, n):\n",
    "            if k == 1:  #只有一枚鸡蛋\n",
    "                return n\n",
    "\n",
    "            if n <= 1:\n",
    "                return n\n",
    "\n",
    "\n",
    "            #从第i楼扔下去\n",
    "            l = 1\n",
    "            r = n + 1\n",
    "            while l + 1 < r:\n",
    "                m = l + (r - l) // 2\n",
    "                if dfs(k, n - m) > dfs(k-1, m-1):\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "\n",
    "            p1 = dfs(k, n - l)\n",
    "            p2 = dfs(k-1, l)\n",
    "\n",
    "            return min(p1, p2) + 1\n",
    "\n",
    "        return dfs(k, n)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        import functools\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def solve(i, j):\n",
    "            if i == 1:\n",
    "                return 0\n",
    "            if j == 0:\n",
    "                return 1e5\n",
    "            l = 1\n",
    "            r = i\n",
    "            ans1 = 1\n",
    "            ans2 = 1\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                if solve(mid, j - 1) < solve(i - mid, j):\n",
    "                    ans1 = mid\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    ans2 = mid\n",
    "                    r = mid\n",
    "            return min(max(solve(ans1, j - 1), solve(i - ans1, j)), max(solve(ans2, j - 1), solve(i - ans2, j))) + 1\n",
    "        return solve(n + 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        # k个鸡蛋 抛t次，最少可以确定n层楼\n",
    "        @cache\n",
    "        def dfs(k,n):\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            \n",
    "            # 只剩一个鸡蛋，只能一层一层地试\n",
    "            if k == 1:\n",
    "                return dfs(k,n-1) + 1\n",
    "                                                  \n",
    "            # dfs(k-1,f-1) 随着f越大函数值越大\n",
    "            # dfs(k,n-f) 随着f越大函数值越小\n",
    "            # 一个单调递增，一个单调递减，求最大最小值，则两个函数值越接近越好，如 3 1 最大为3，2 2 最大值为2\n",
    "            # 二分求f\n",
    "            start = 1\n",
    "            end = n\n",
    "            while start <= end:\n",
    "                middle = (start + end) // 2\n",
    "                # 递增比递减小，则增大f值\n",
    "                if dfs(k-1,middle-1) < dfs(k,n-middle):\n",
    "                    start = middle + 1\n",
    "                else:\n",
    "                    end = middle - 1\n",
    "            \n",
    "            f = start\n",
    "            \n",
    "            # 从每一层楼扔下\n",
    "            #for f in range(1,n+1):               \n",
    "            #    res = min (res,max(dfs(k-1,f-1),dfs(k,n-f))+1)\n",
    "            \n",
    "            return dfs(k-1,f-1) + 1\n",
    "                \n",
    "        \n",
    "        return dfs(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        if k==1:\n",
    "            return n\n",
    "        if n==0:\n",
    "            return 0\n",
    "        memo = [[-666]*(n+1)for _ in range(k+1)]\n",
    "        def dp(k,n):\n",
    "            if k==1:\n",
    "                return n\n",
    "            if n==0:\n",
    "                return 0\n",
    "            if memo[k][n] != -666:\n",
    "                return memo[k][n]\n",
    "            res = float(\"inf\")\n",
    "            left, right = 1, n\n",
    "            while left<=right:\n",
    "                mid = (left+right)//2\n",
    "                broker = dp(k-1, mid-1)\n",
    "                no_borker = dp(k, n-mid)\n",
    "                if broker>no_borker:\n",
    "                    right = mid-1\n",
    "                    res = min(res, broker+1)\n",
    "                else:\n",
    "                    left = mid+1\n",
    "                    res= min(res, no_borker+1)\n",
    "            memo[k][n] = res\n",
    "            return res\n",
    "        return  dp(k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        def dp(k,n):\n",
    "            if (k,n) in memo:\n",
    "                return memo[(k,n)]\n",
    "            if n==0:\n",
    "                return 0\n",
    "            if k==1:\n",
    "                return n\n",
    "            ans=float('inf')\n",
    "            \n",
    "            # for i in range(1,n+1):\n",
    "            #     broken=dp(k-1,i-1)\n",
    "            #     not_broken=dp(k,n-i)\n",
    "            #     ans=min(ans,max(broken,not_broken)+1)\n",
    "            \n",
    "            l,r=1,n\n",
    "            while l<=r:\n",
    "                mid=(r-l)//2+l\n",
    "                broken=dp(k-1,mid-1)\n",
    "                not_broken=dp(k,n-mid)\n",
    "                if broken>not_broken:\n",
    "                    r=mid-1\n",
    "                    ans=min(ans,broken+1)\n",
    "                else:\n",
    "                    l=mid+1\n",
    "                    ans=min(ans,not_broken+1)\n",
    "            \n",
    "\n",
    "            memo[(k,n)]=ans\n",
    "            return ans\n",
    "        \n",
    "        memo={}\n",
    "        return dp(k,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        d = {}\n",
    "        def dp(k, n):\n",
    "            if n == 0 :\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if (k, n) not in d:\n",
    "                minv=  10**9\n",
    "                l = 1\n",
    "                r = n \n",
    "                while l<r:\n",
    "                    mid = (l+r+1)//2\n",
    "                    if(dp(k-1,mid-1) <= dp(k,n-mid)):\n",
    "                        l = mid\n",
    "                    else:\n",
    "                        r = mid-1\n",
    "                d[(k, n)] =  max(dp(k-1,l-1) , dp(k,n - l) ) \n",
    "                if l != n :\n",
    "                    d[(k,n)] = min(d[(k,n)] , max(dp(k-1,l),dp(k,n-l-1)))\n",
    "                d[(k,n)] += 1\n",
    "            return d[(k, n)]\n",
    "\n",
    "        return dp(k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K: int, N: int) -> int:\n",
    "        memo = dict()\n",
    "        def dp(K, N) -> int:\n",
    "            # base case\n",
    "            if K == 1: return N\n",
    "            if N == 0: return 0\n",
    "            # 避免重复计算\n",
    "            if (K, N) in memo:\n",
    "                return memo[(K, N)]\n",
    "\n",
    "            res = float('INF')\n",
    "            # # 穷举所有可能的选择\n",
    "            # for i in range(1, N + 1):\n",
    "            #     res = min(res, \n",
    "            #                 max(\n",
    "            #                     dp(K, N - i), \n",
    "            #                     dp(K - 1, i - 1)\n",
    "            #                     ) + 1\n",
    "            #             )\n",
    "            res = float('INF')\n",
    "            \n",
    "        # 用二分搜索代替线性搜索\n",
    "            l, r = 1, N\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                broken = dp(K - 1, mid - 1) # 碎\n",
    "                not_broken = dp(K, N - mid) # 没碎\n",
    "                # res = min(max(碎，没碎) + 1)\n",
    "                if broken > not_broken:\n",
    "                    r = mid - 1\n",
    "                    res = min(res, broken + 1)\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "                    res = min(res, not_broken + 1)\n",
    "\n",
    "            # 记入备忘录\n",
    "            memo[(K, N)] = res\n",
    "            return res\n",
    "    \n",
    "        return dp(K, N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        return self.dp2(k, n)\n",
    "\n",
    "    def recusive(self, k, n):\n",
    "        if k == 1:\n",
    "            return n\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        min_tries = float('inf')\n",
    "        for i in range(1, n+1):\n",
    "            break_case = self.recusive(k-1, i-1)\n",
    "            no_break_case = self.recusive(k, n-i)\n",
    "            worst_case = 1 + max(break_case, no_break_case)\n",
    "            min_tries = min(min_tries, worst_case)\n",
    "        return min_tries\n",
    "\n",
    "    def dp2(self, k, n):\n",
    "        # 使用字典来存储已经计算过的结果，避免重复计算\n",
    "        memo = {}\n",
    "\n",
    "        def helper(k, n):\n",
    "            # 如果只有1个鸡蛋，需要从第1层开始逐层测试\n",
    "            if k == 1:\n",
    "                return n\n",
    "            # 如果没有楼层或只有1层，返回n\n",
    "            if n == 0 or n == 1:\n",
    "                return n\n",
    "\n",
    "            # 如果这个状态已经计算过，直接返回结果\n",
    "            if (k, n) in memo:\n",
    "                return memo[(k, n)]\n",
    "\n",
    "            # 使用二分搜索来加速计算\n",
    "            low, high, result = 1, n, n\n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "\n",
    "                # 当鸡蛋破裂时，我们需要在下面的楼层继续测试\n",
    "                breaks = helper(k - 1, mid - 1)\n",
    "                # 当鸡蛋没有破裂时，我们需要在上面的楼层继续测试\n",
    "                not_break = helper(k, n - mid)\n",
    "\n",
    "                # 我们需要的是最坏情况下的移动次数，所以取两者中的最大值\n",
    "                worst = 1 + max(breaks, not_break)\n",
    "\n",
    "                # 使用二分搜索来调整搜索范围\n",
    "                if breaks > not_break:\n",
    "                    high = mid - 1\n",
    "                    result = min(result, worst)\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "                    result = min(result, worst)\n",
    "\n",
    "            # 保存结果并返回\n",
    "            memo[(k, n)] = result\n",
    "            return result\n",
    "\n",
    "        return helper(k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, K: int, N: int) -> int:\n",
    "        memo = dict()\n",
    "        def dp(K, N):\n",
    "            if K == 1: return N\n",
    "            if N == 0: return 0\n",
    "            if (K, N) in memo:\n",
    "                return memo[(K, N)]\n",
    "                                \n",
    "            # for 1 <= i <= N:\n",
    "            #     res = min(res, \n",
    "            #             max( \n",
    "            #                 dp(K - 1, i - 1), \n",
    "            #                 dp(K, N - i)      \n",
    "            #                 ) + 1 \n",
    "            #             )\n",
    "\n",
    "            res = float('INF')\n",
    "            # 用二分搜索代替线性搜索\n",
    "            lo, hi = 1, N\n",
    "            while lo <= hi:\n",
    "                mid = (lo + hi) // 2\n",
    "                broken = dp(K - 1, mid - 1) # 碎\n",
    "                not_broken = dp(K, N - mid) # 没碎\n",
    "                # res = min(max(碎，没碎) + 1), 相当于求最坏的情况下的最少次数\n",
    "                if broken > not_broken:\n",
    "                    hi = mid - 1\n",
    "                    res = min(res, broken + 1)\n",
    "                else:\n",
    "                    lo = mid + 1\n",
    "                    res = min(res, not_broken + 1)\n",
    "\n",
    "            memo[(K, N)] = res\n",
    "            return res\n",
    "        return dp(K, N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dic1 = {}\n",
    "        def dp(K, N):\n",
    "            if K ==1: return N\n",
    "            if N ==0: return 0\n",
    "            if (K,N) in dic1:return dic1[(K,N)]\n",
    "            '''\n",
    "            res = float('INF')\n",
    "            for i in range(1,N+1):\n",
    "                print('res',res)\n",
    "                res = min( max(dp(K-1,i-1), dp(K,N-i))+1, res )\n",
    "            dic1[(K,N)] = res\n",
    "            '''\n",
    "            res = float('INF')\n",
    "            \n",
    "            lo, hi =1, N\n",
    "            while lo <= hi:\n",
    "                print(lo)\n",
    "                mid = (lo + hi)//2\n",
    "                broken = dp(K-1,mid-1)\n",
    "                nonbroken =  dp(K,N-mid)\n",
    "                if broken > nonbroken:\n",
    "                    hi = mid - 1\n",
    "                    res = min(broken+1,res) \n",
    "                else:\n",
    "                    lo = mid + 1\n",
    "                    res = min(nonbroken+1,res) \n",
    "            dic1[(K,N)] = res\n",
    "            return res\n",
    "\n",
    "        return dp(k,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[0] * (n+1) for _ in range(k+1)]\n",
    "        for i in range(1, k+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = j\n",
    "        for i in range(2, k+1):\n",
    "            for j in range(2, n+1):\n",
    "                le, ri = 1, j\n",
    "                while le <= ri:\n",
    "                    mid = le + (ri - le)//2\n",
    "                    if dp[i-1][mid-1] >= dp[i][j-mid]:\n",
    "                        ri = mid - 1\n",
    "                    else:\n",
    "                        le = mid + 1\n",
    "                dp[i][j] = max(dp[i-1][le-1], dp[i][j-le]) + 1\n",
    "        return dp[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[x for x in range(n + 1)] for x in range(k + 1)]\n",
    "        for i in range(2, k + 1):\n",
    "            for j in range(2, n + 1):\n",
    "                l, r = 0, j // 2 + 1 # 倾向于从低层扔鸡蛋，以谋取碎与不碎的平衡\n",
    "                while l < r - 1:\n",
    "                    mid = l + r >> 1\n",
    "                    # 从 mid + 1 层扔鸡蛋，如果碎了，f <= mid, 否则 f >= mid + 1\n",
    "                    if dp[i - 1][mid] < dp[i][j - mid - 1]:\n",
    "                        l = mid\n",
    "                    else:\n",
    "                        r = mid\n",
    "                dp[i][j] = min(dp[i][j - l - 1], dp[i - 1][r]) + 1\n",
    "        return dp[k][n]\n",
    "\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[x for x in range(n + 1)] for x in range(k + 1)]\n",
    "        for i in range(2, k + 1):\n",
    "            p = 0\n",
    "            for j in range(2, n + 1):\n",
    "                while dp[i - 1][p] < dp[i][j - p - 1]:\n",
    "                    p += 1\n",
    "                dp[i][j] = min(dp[i][j - p], dp[i - 1][p]) + 1\n",
    "        return dp[k][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        dp = [[-1] * (n + 1) for _ in range(k + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            dp[1][i] = i\n",
    "\n",
    "        def egg_num(kk, nn):\n",
    "            nonlocal dp\n",
    "\n",
    "            if dp[kk][nn] != -1:\n",
    "                return dp[kk][nn]\n",
    "            if nn == 0:\n",
    "                dp[kk][nn] = 0\n",
    "                return 0\n",
    "            if kk == 1:\n",
    "                dp[kk][nn] = nn\n",
    "                return nn\n",
    "            low, high = 1, nn\n",
    "\n",
    "            while low + 1 < high:\n",
    "                x = (low + high) // 2\n",
    "                t1 = egg_num(kk - 1, x - 1)\n",
    "                t2 = egg_num(kk, nn - x)\n",
    "                if t1 < t2:\n",
    "                    low = x\n",
    "                elif t1 > t2:\n",
    "                    high = x\n",
    "                else:\n",
    "                    low = high = x\n",
    "            dp[kk][nn] = 1 + min(max(egg_num(kk - 1, x - 1), egg_num(kk, nn - x)) for x in (low, high) )\n",
    "            return dp[kk][nn]\n",
    "        res = egg_num(k, n)\n",
    "        # print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(k: int, n: int):\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return n\n",
    "            l = 1\n",
    "            r = n\n",
    "\n",
    "            while l <= r:\n",
    "                mid = (l + r) >> 1\n",
    "\n",
    "                left = dfs(k - 1, mid - 1)\n",
    "                right = dfs(k, n - mid)\n",
    "\n",
    "                if left <= right:\n",
    "                    l = mid + 1\n",
    "                elif left > right:\n",
    "                    r = mid - 1\n",
    "\n",
    "            return 1 + min(\n",
    "                max(dfs(k - 1, x - 1), dfs(k, n - x)) for x in (l, l - 1) if 1 <= x <= n\n",
    "            )\n",
    "\n",
    "        return dfs(k, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(k : int, N : int):\n",
    "            if k == 1: return N\n",
    "            if N == 0: return 0\n",
    "            l, r = 1, N\n",
    "            res = float('INF')\n",
    "            # 用二分搜索代替线性搜索\n",
    "            lo, hi = 1, N\n",
    "            while (lo <= hi):\n",
    "                mid = (lo + hi) >> 1\n",
    "                broken = dfs(k - 1, mid - 1)\n",
    "                notBroken = dfs(k, N - mid)\n",
    "                if broken > notBroken:\n",
    "                    res = min(res, broken + 1)\n",
    "                    hi = mid - 1\n",
    "                else:\n",
    "                    res = min(res, notBroken + 1)\n",
    "                    lo = mid + 1\n",
    "            return res\n",
    "        return dfs(k, n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
